#include <bits/stdc++.h>
using namespace std;

/*
342. 4的幂
已解答
简单
相关标签
premium lock icon
相关企业
给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x

 

示例 1：

输入：n = 16
输出：true
示例 2：

输入：n = 5
输出：false
示例 3：

输入：n = 1
输出：true
 

提示：

-231 <= n <= 231 - 1
 

进阶：你能不使用循环或者递归来完成本题吗？
*/

// 法一
class Solution {
public:
    bool isPowerOfFour(int n) {
        // 递归
        if (n <= 0) return false;
        if (n == 1) return true;
        if (n % 4 != 0) return false;

        return isPowerOfFour(n / 4);
    }
};

// 法二
class Solution {
public:
    bool isPowerOfFour(int n) {
        // 循环
        if (n <= 0) return false;
        while (n > 1) {
            if (n % 4 != 0) return false;
            n /= 4;
        }

        return n == 1;
    }
};

// 法三
class Solution {
public:
    bool isPowerOfFour(int n) {
        // 位运算 
        // 4 的 幂在二进制 都是(奇数位置)【0X55555555】 所以 我 可以 >> 11两个
        if (n <= 0 || (n & (n - 1)) != 0)       return false;
        return (n & 0X55555555) != 0;
    }
};